package com.linwen.excise.leetcode;

/**
 * @ClassName _57和为s的连续正数序列
 * @Description 和为s的连续正数序列
 * @Author lin
 * @Date 2022/2/24 下午11:21
 * @Version V1.0
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 * 示例 1：
 *
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 * */

public class _57和为s的连续正数序列 {
    public static void main(String[] args) {
        int n = 15;
        int[][] ints = findContinuousSequence(n);
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j < ints[i].length; j++) {
                System.out.print(ints[i][j]+" ");
            }
            System.out.println();
        }

    }
    public static int[][] findContinuousSequence(int target) {
        // 滑动窗口
        ArrayList<Object> list = new ArrayList<>();
        int sum = 0;
        for (int i = 1; i <= target/2; i++) {
            for (int j = i;; j++) {
                sum += j;
                if(sum>target){// sum太大了  直接跳出
                    sum = 0;
                    break;
                }else if(sum==target){// sum正好 将i---j的连续数存起来
                    int[] arr = new int[j-i+1];
                    for (int k = 0; k <j-i+1 ; k++) {
                        arr[k] = k+i;
                    }
                    list.add(arr);
                    sum = 0;
                    break;
                }
            }
        }

        return list.toArray(new int[list.size()][]);

    }
}
